#include <iostream>
using namespace std;
const int N=1010;
int n,V,v[N],w[N];

int dp[N][N];

int main()
{
  cin>>n>>V;
  for(int i=0;i<=n;i++)
    cin>>v[i]>>w[i];
  for(int i=1;i<=n;i++)
  {
    for(int j=1;j<=V;j++)
    {
      dp[i][j]=dp[i-1][j];
      if(j>=v[i])
        dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
    }
    cout<<dp[n][V]<<endl;
  }
  return 0;
}
